`
https://leetcode.cn/problems/combination-sum-ii/
`

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  const res = []

  const track = []
  let trackSum = 0

  // 元素有重复，预先排序，方便剪枝
  candidates.sort((a, b) => a - b)

  const backtrack = (start) => {
    // 符合条件，记录组合
    if (trackSum === target) {
      res.push([...track])
    }

    // 总和超过 target 直接返回
    if (trackSum > target) {
      return
    }

    for (let i = start; i < candidates.length; i++) {
      // 剪枝，剪掉遇到的第一个相同元素
      if (i > start && candidates[i] === candidates[i - 1]) continue

      trackSum += candidates[i]
      track.push(candidates[i])
      backtrack(i + 1)
      track.pop()
      trackSum -= candidates[i]
    }
  }

  backtrack(0)
  return res
};